package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

// 剑指 Offer 17. 打印从1到最大的n位数
// https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/
class DaYinCong1daoZuiDaDeNweiShuLcof {
    public static void main(String[] args) {
        Solution solution = new DaYinCong1daoZuiDaDeNweiShuLcof().new Solution();
        solution.printNumbers(2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int[] printNumbers(int n) {
            int total = (int) (Math.pow(10, n) - 1);
            int[] res = new int[total];
            for (int i = 0; i < total; i++) {
                res[i] = i + 1;
            }

            return res;
        }*/


        int nineCount = 0, count = 0, start, n;
        int[] res;
        char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

        public int[] printNumbers(int n) {
            this.n = n;
            res = new int[(int) Math.pow(10, n) - 1];
            start = n - 1; // 从个位开始
            num = new char[n];
            dfs(0);
            return res;
        }

        public void dfs(int x) {
            if (n == x) {
                // 前面的0使用start标志，表示舍弃多少个0
                String s = String.valueOf(num).substring(start);

                // 直接跳过0，从1开始
                if (!s.equals("0")) {
                    res[count++] = Integer.parseInt(s);
                }

                // 如果总位数减去前面0的位数等于都为9的位数，需要扩大一位
                // 例如999，此时下一个数就是1000，start需要减一
                if (n - start == nineCount) start--;
                return;
            }

            for (char c : loop) {
                // 9的个数加一
                if (c == '9') nineCount++;
                num[x] = c;
                // 递归下一位数
                dfs(x + 1);
            }
            // 注意减去9的数量，回溯
            nineCount--;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
